package sortedset

import (
	"math"
	"math/rand"
)

const (
	maxLevel = 16
)

type Elem struct {
	Key   string
	Score float64
}

type Forward struct {
	node   *node
	weight int64
}

type node struct {
	Elem
	forwards []Forward
	backward *node
}

func newNode(key string, score float64, level int16) *node {
	return &node{
		Elem: Elem{
			Key:   key,
			Score: score,
		},
		forwards: make([]Forward, level),
		backward: nil,
	}
}

func equal(val1 float64, val2 float64, eps float64) bool {
	return math.Abs(val1-val2) < eps
}

// lessThan priority: score -> key.
func (n *node) lessThan(key string, score float64) bool {
	const eps = 1e-8
	if !equal(n.Score, score, eps) {
		return n.Score < score
	}
	return n.Key < key
}

type skipList struct {
	header  *node // a node with minimum score and maximum level as the search starting point
	trailer *node // the last inserted node
	length  int64 // number of nodes
	level   int16 // the highest node's level apart from header
}

func newSkipList() *skipList {
	return &skipList{
		header:  newNode("", 0, maxLevel),
		trailer: nil,
		length:  0,
		level:   1,
	}
}

func randomLevel() int16 {
	level := int16(1)
	for float32(rand.Int31()&0xFFFF) < (0.25 * 0xFFFF) {
		level++
	}
	if level < maxLevel {
		return level
	}
	return maxLevel
}

func (l *skipList) insert(key string, score float64) *node {
	// Which nodes to insert after for every level.
	update := make([]*node, maxLevel)
	// rank[i]: sum of arc's weight when search the target.
	// 		increment forwards[i].weight when move right
	//		increment 0 when move down
	// rank[l.level] = 0 as the sentry for unifying code.
	rank := make([]int64, maxLevel+1)

	// Find a position to insert after.
	// 		move right: current = current.forwards[i].node
	// 		move down:  i--
	current := l.header
	for i := l.level - 1; i >= 0; i-- {
		rank[i] = rank[i+1]
		// Find the rightest node less than `score` or `key` as `update[i]`.
		for current.forwards[i].node != nil && current.forwards[i].node.lessThan(key, score) {
			rank[i] += current.forwards[i].weight
			current = current.forwards[i].node
		}
		update[i] = current
	}

	level := randomLevel() // inserted node's level
	// Extend l's level if node level is bigger.

	// weight of update[i]->node[i]: l.length
	if level > l.level {
		for i := l.level; i < level; i++ {
			rank[i] = 0
			update[i] = l.header
			update[i].forwards[i].weight = l.length
		}
		l.level = level
	}

	// Generate a new node and then insert its link after `update`.
	inserted := newNode(key, score, level)
	for i := int16(0); i < level; i++ {
		inserted.forwards[i].node = update[i].forwards[i].node
		update[i].forwards[i].node = inserted

		// rank[0] - rank[i]: sum of weight in search path from update[i] to update[0]
		// Weight stores difference of cost in searching path.
		// So sum of weights is the total cost in searching path.
		inserted.forwards[i].weight = update[i].forwards[i].weight - (rank[0] - rank[i])
		update[i].forwards[i].weight = (rank[0] - rank[i]) + 1
	}

	// Increment weight for untouched levels.
	for i := level; i < l.level; i++ {
		update[i].forwards[i].weight++
	}

	// Set backward for inserted node.
	if update[0] == l.header {
		inserted.backward = nil
	} else {
		inserted.backward = update[0]
	}
	if inserted.forwards[0].node != nil {
		inserted.forwards[0].node.backward = inserted
	} else {
		l.trailer = inserted
	}
	l.length++

	return current
}

func (l *skipList) removeNode(node *node, update []*node) {
	for i := int16(0); i < l.level; i++ {
		if update[i].forwards[i].node == node {
			update[i].forwards[0].weight += node.forwards[0].weight - 1
			update[i].forwards[i].node = node.forwards[i].node
		} else {
			update[i].forwards[0].weight--
		}
	}
	if node.forwards[0].node != nil {
		node.forwards[0].node.backward = node.backward
	} else {
		l.trailer = node.backward
	}
	for l.level > 1 && l.header.forwards[l.level-1].node == nil {
		l.level--
	}
	l.length--
}

func (l *skipList) remove(key string, score float64) bool {
	/*
	 * find backward node (of target) or last node of each level
	 * their forward need to be updated
	 */
	update := make([]*node, maxLevel)
	node := l.header
	for i := l.level - 1; i >= 0; i-- {
		for node.forwards[i].node != nil &&
			(node.forwards[i].node.Score < score ||
				(node.forwards[i].node.Score == score &&
					node.forwards[i].node.Key < key)) {
			node = node.forwards[i].node
		}
		update[i] = node
	}
	node = node.forwards[0].node
	if node != nil && score == node.Score && node.Key == key {
		l.removeNode(node, update)
		// free x
		return true
	}
	return false
}

func (l *skipList) getRank(key string, score float64) int64 {
	var rank int64 = 0
	x := l.header
	for i := l.level - 1; i >= 0; i-- {
		for x.forwards[i].node != nil &&
			(x.forwards[i].node.Score < score ||
				(x.forwards[i].node.Score == score &&
					x.forwards[i].node.Key <= key)) {
			rank += x.forwards[i].weight
			x = x.forwards[i].node
		}

		/* x might be equal to zsl->header, so test if obj is non-NULL */
		if x.Key == key {
			return rank
		}
	}
	return 0
}

func (l *skipList) getByRank(rank int64) *node {
	var r int64 = 0
	n := l.header
	// scan from top level
	for i := l.level - 1; i >= 0; i-- {
		for n.forwards[i].node != nil && (r+n.forwards[i].weight) <= rank {
			r += n.forwards[i].weight
			n = n.forwards[i].node
		}
		if r == rank {
			return n
		}
	}
	return nil
}

func (l *skipList) hasInRange(min ScoreBorder, max ScoreBorder) bool {
	// min & max = empty
	if min.Value > max.Value || (min.Value == max.Value && (min.Exclusive || max.Exclusive)) {
		return false
	}
	// min > tail
	n := l.trailer
	if n == nil || !min.LT(n.Score) {
		return false
	}
	// max < head
	n = l.header.forwards[0].node
	if n == nil || !max.GT(n.Score) {
		return false
	}
	return true
}

func (l *skipList) getFirstInScoreRange(min ScoreBorder, max ScoreBorder) *node {
	if !l.hasInRange(min, max) {
		return nil
	}
	n := l.header
	// scan from top level
	for i := l.level - 1; i >= 0; i-- {
		// if forward is not in range than move forward
		for n.forwards[i].node != nil && !min.LT(n.forwards[i].node.Score) {
			n = n.forwards[i].node
		}
	}
	/* This is an inner range, so the next node cannot be NULL. */
	n = n.forwards[0].node
	if !max.GT(n.Score) {
		return nil
	}
	return n
}

func (l *skipList) getLastInScoreRange(min ScoreBorder, max ScoreBorder) *node {
	if !l.hasInRange(min, max) {
		return nil
	}
	n := l.header
	// scan from top level
	for i := l.level - 1; i >= 0; i-- {
		for n.forwards[i].node != nil && max.GT(n.forwards[i].node.Score) {
			n = n.forwards[i].node
		}
	}
	if !min.LT(n.Score) {
		return nil
	}
	return n
}

func (l *skipList) RemoveRangeByScore(min ScoreBorder, max ScoreBorder) (removedKeys []string) {
	update := make([]*node, maxLevel)
	removedKeys = make([]string, 0)
	// find backward nodes (of target range) or last node of each level
	node := l.header
	for i := l.level - 1; i >= 0; i-- {
		for node.forwards[i].node != nil {
			if min.LT(node.forwards[i].node.Score) { // already in range
				break
			}
			node = node.forwards[i].node
		}
		update[i] = node
	}

	// node is the first one within range
	node = node.forwards[0].node

	// remove nodes in range
	for node != nil {
		if !max.GT(node.Score) { // already out of range
			break
		}
		next := node.forwards[0].node
		removedKeys = append(removedKeys, node.Key)
		l.removeNode(node, update)
		node = next
	}
	return removedKeys
}

func (l *skipList) RemoveRangeByRank(start int64, stop int64) (removedKeys []string) {
	var r int64 = 0 // rank of iterator
	update := make([]*node, maxLevel)
	removedKeys = make([]string, 0)

	// scan from top level
	node := l.header
	for i := l.level - 1; i >= 0; i-- {
		for node.forwards[i].node != nil && (r+node.forwards[i].weight) < start {
			r += node.forwards[i].weight
			node = node.forwards[i].node
		}
		update[i] = node
	}

	r++
	node = node.forwards[0].node // first node in range

	// remove nodes in range
	for node != nil && r < stop {
		next := node.forwards[0].node
		removedKeys = append(removedKeys, node.Key)
		l.removeNode(node, update)
		node = next
		r++
	}
	return removedKeys
}
